<!DOCTYPE html>
<html>
<!--
Copyright 2011 Google Inc.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

     http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-->
<head>
<title>document.observeOwnedNodes test</title>
<script src="../third_party/closure/closure/goog/base.js"></script>
<script src="weak_map.js"></script>
<script src="document_observe_owned_nodes.js"></script>
<script src="document_observe_projections.js"></script>

<script>
goog.require('goog.testing.jsunit');
</script>
</head>
<body>
  <div id="test-div"></div>

<script>

var testDiv;
var tracker;
var fastTracker;

function startObserving() {
  tracker = new MutationTracker(testDiv);
  fastTracker = new FastMutationTracker(testDiv);
  document.observeOwnedNodes(fastTracker.observer);
}

function stopObserving() {
  document.stopObservingOwnedNodes(fastTracker.observer);
}

function setUp() {
  testDiv = document.getElementById('test-div');
}

function tearDown() {
  stopObserving();
  testDiv.textContent = '';
}

function compareNodeArrayIgnoreOrder(expected, actual) {
  assertEquals(expected.length, actual.length);
  expected.forEach(function(node) {
    assertTrue(actual.indexOf(node) >= 0);
  });
}

function compareTrackersAndGetChanges() {
  document.deliverMutations();

  function getChanges(tracker) {
    return {
      changedParent: tracker.getChangedParent(),
      added: tracker.getAdded(),
      removed: tracker.getRemoved(),
      childlistChanges: tracker.getChildlistChanges()
    }
  }

  var changes = getChanges(tracker);
  var fastChanges = getChanges(fastTracker);

  tracker.reset();
  fastTracker.reset();

  Object.keys(changes).forEach(function(key) {
    compareNodeArrayIgnoreOrder(changes[key], fastChanges[key]);
  });

  return changes;
}

function assertAddedMovedRemoved(expectAdded, expectMoved, expectRemoved) {
  var changes = compareTrackersAndGetChanges();

  var addedMap = new WeakMap;
  changes.added.forEach(function(el) {
    addedMap.set(el, true);
  });

  var moved = [];
  changes.childlistChanges.forEach(function(el) {
    if (!addedMap.has(el))
      moved.push(el);
  });

  compareNodeArrayIgnoreOrder(expectAdded, changes.added);
  compareNodeArrayIgnoreOrder(expectRemoved, changes.removed);
  compareNodeArrayIgnoreOrder(expectMoved, moved);
}

function testAddRemoveBasic() {
  startObserving();

  var div = testDiv.appendChild(document.createElement('div'));
  var span = div.appendChild(document.createElement('span'));
  assertAddedMovedRemoved([div, span], [], []);

  div.removeChild(span);
  assertAddedMovedRemoved([], [], [span]);
}

function testAddAndRemoveOutsideTree() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var span = div2.appendChild(document.createElement('span'));

  startObserving();
  testDiv.removeChild(div1);
  // This add will be ignored since this is a detached subtree.
  div1.appendChild(document.createElement('span'));
  div1.removeChild(div2);
  div2.removeChild(span);
  assertAddedMovedRemoved([], [], [div1, div2, span]);

  // This add will be ignored because it happens outside the document tree.
  div1.appendChild(document.createElement('span'));
  var mutationsDelivered = false;
  assertAddedMovedRemoved([], [], []);
}

function testAddOutsideOfTreeAndReinsert() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));

  startObserving();
  testDiv.removeChild(div1);
  // This add is taking place while outside the tree, but should be considered
  // and 'add' because the parent node is later replaced.
  var span = div1.appendChild(document.createElement('span'));
  testDiv.appendChild(div1);
  assertAddedMovedRemoved([span], [], []);
}

function testMove() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var span = div2.appendChild(document.createElement('span'));

  startObserving();

  testDiv.removeChild(div1);
  div1.removeChild(div2);
  testDiv.appendChild(div2);
  testDiv.appendChild(div1);

  assertAddedMovedRemoved([], [div2], []);
}

function testAddingToDetachedSubtree() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));

  startObserving();
  testDiv.removeChild(div1);
  var div2 = document.createElement('div');
  var span = document.createElement('span');
  div1.appendChild(div2);
  div2.appendChild(span);

  assertAddedMovedRemoved([], [], [div1]);
}

function testReorderInsideTree() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = div2.appendChild(document.createElement('div'));

  startObserving();

  testDiv.removeChild(div1);
  div1.removeChild(div2);
  div2.removeChild(div3);
  testDiv.appendChild(div3);
  div3.appendChild(div2);
  div2.appendChild(div1);

  assertAddedMovedRemoved([], [div1, div2, div3], []);
}

function testReorderInsideTreeAndAddMiddle() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = div2.appendChild(document.createElement('div'));

  startObserving();

  testDiv.removeChild(div1);
  div1.removeChild(div2);
  div2.removeChild(div3);
  testDiv.appendChild(div3);
  div3.appendChild(div2);
  var div4 = document.createElement('div');
  div2.appendChild(div4);
  div4.appendChild(div1);

  assertAddedMovedRemoved([div4], [div1, div2, div3], []);
}

function testReorderOutsideTree() {
  // Setup
  var div1 = document.createElement('div');
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = div2.appendChild(document.createElement('div'));

  startObserving();

  div1.removeChild(div2);
  div2.removeChild(div3);
  div3.appendChild(div2);
  div2.appendChild(div1);

  assertAddedMovedRemoved([], [], []);
}

function testReorderAndRemoveFromTree() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = div2.appendChild(document.createElement('div'));

  startObserving();

  testDiv.removeChild(div1);
  div1.removeChild(div2);
  div2.removeChild(div3);
  div3.appendChild(div2);
  div2.appendChild(div1);

  assertAddedMovedRemoved([], [], [div1, div2, div3]);
}

function testReorderAndRemoveSubtree() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));

  startObserving();

  div1.removeChild(div2);
  testDiv.appendChild(div2);
  div2.appendChild(div1);
  div2.removeChild(div1);

  assertAddedMovedRemoved([], [div2], [div1]);
}

function testReorderOutsideAndAddToTree() {
  // Setup
  var div1 = document.createElement('div');
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = div2.appendChild(document.createElement('div'));

  startObserving();

  div1.removeChild(div2);
  div2.removeChild(div3);
  div3.appendChild(div2);
  div2.appendChild(div1);
  testDiv.appendChild(div3);

  assertAddedMovedRemoved([div1, div2, div3], [], []);
}

function testReorderOutsideAndAddSubtree() {
  // Setup
  var div1 = document.createElement('div');
  var div2 = div1.appendChild(document.createElement('div'));

  startObserving();

  div1.removeChild(div2);
  div2.appendChild(div1);
  testDiv.appendChild(div1);

  assertAddedMovedRemoved([div1], [], []);
}

function testRemoveSubtreeAndAddToExternal() {
  // Setup
  var div1 = testDiv.appendChild(document.createElement('div'));
  var div2 = div1.appendChild(document.createElement('div'));
  var div3 = document.createElement('div');

  startObserving();
  testDiv.removeChild(div1);
  div3.appendChild(div1);

  assertAddedMovedRemoved([], [], [div1, div2]);
}

function testMoveDetectNoop() {
  // Setup
  var divA = testDiv.appendChild(document.createElement('div'));
  divA.id = 'a';
  var divB = testDiv.appendChild(document.createElement('div'));
  divB.id = 'b';
  var divC = testDiv.appendChild(document.createElement('div'));
  divC.id = 'c';
  var divD = testDiv.appendChild(document.createElement('div'));
  divD.id = 'd';
  var divE = testDiv.appendChild(document.createElement('div'));
  divE.id = 'e';
  var divF = testDiv.appendChild(document.createElement('div'));
  divE.id = 'f';
  var divG = document.createElement('div');
  divG.id = 'g';

  startObserving();                 // A  B  C  D  E  F

  insertAfter(testDiv, divD, divA); // A [D] B  C  E  F
  insertAfter(testDiv, divC, divA); // A [C  D] B  E  F
  insertAfter(testDiv, divB, divC); // A [C  B  D] E  F
  insertAfter(testDiv, divD, divA); // A [D  C  B] E  F
  insertAfter(testDiv, divG, divE); // A [D  C  B] E [G] F
  insertAfter(testDiv, divE, divG); // A [D  C  B  G  E] F

  // Final effect is A [D C] B [G] E F

  assertAddedMovedRemoved([divG], [divD, divC], []);
}

// FUZZER

function randInt(start, end) {
  return Math.round(Math.random() * (end-start) + start);
}

var tagMenu = [
  'DIV',
  'SPAN',
  'P'
];

var nodePrivateIdCounter = 1;

function randomNode() {
  var node = document.createElement(tagMenu[randInt(0, tagMenu.length - 1)]);
  node.__id__ = nodePrivateIdCounter++;
  return node;
}

function randDist(count, amount) {
  var buckets = [];

  while(count-- > 0)
    buckets[count] = 0;

  while (amount > 0) {
    var add = randInt(0, 1);
    buckets[randInt(0, buckets.length - 1)] += add;
    amount -= add;
  }

  return buckets;
}

var MAX_CHILDREN = 8;

function randomTree(root, numNodes) {
  if (numNodes <= 0)
    return;

  var childCount = Math.min(numNodes, MAX_CHILDREN);
  var childDist = randDist(childCount, numNodes - childCount);
  for (var i = 0; i < childDist.length; i++) {
    var child = root.appendChild(randomNode());
    child.id = root.id + '.' + String.fromCharCode(65 + i);  // asci('A') + i.
    randomTree(child, childDist[i]);
  }
}

function assertTreesEqual(node, copy) {
  assertEquals(node.tagName, copy.tagName);
  assertEquals(node.id, copy.id);
  assertEquals(node.childNodes.length, copy.childNodes.length);
  for (var i = 0; i < node.childNodes.length; i++) {
    assertTreesEqual(node.childNodes[i], copy.childNodes[i]);
  }
}

function testRandomCloneAndTestCopy() {
  randomTree(testDiv, 512);
  var copy = testDiv.cloneNode(true);
  assertTreesEqual(testDiv, copy);
}

function getReachable(root, reachable, excludeRoot) {
  reachable = reachable || [];
  if (!excludeRoot)
    reachable.push(root);
  if (!root.childNodes || ! root.childNodes.length)
    return;

  for (var i = 0; i < root.childNodes.length; i++) {
    getReachable(root.childNodes[i], reachable);
  }

  return reachable;
}

function nodeIsDescendant(root, target) {
  if (!target)
    return false;
  if (root === target)
    return true;

  return nodeIsDescendant(root, target.parentNode);
}

function selectNodeAtRandom(nodes, excludeNodeAndDescendants) {
  var node;
  while (!node || nodeIsDescendant(excludeNodeAndDescendants, node))
    node = nodes[randInt(0, nodes.length - 1)];
  return node;
}

function removeNodeAtRandom(nonRootNodes) {
  var node = selectNodeAtRandom(nonRootNodes);
  var parent = node.parentNode;
  return node;
}

function insertNodeAtRandom(allNodes, node) {
  var parent = selectNodeAtRandom(allNodes, node);
  // NOTE: The random index here maybe be childNodes[childNodes.length]
  // which is undefined, meaning 'insert at end of childlist'.
  var beforeNode = parent.childNodes[randInt(0, parent.childNodes.length)];
  parent.insertBefore(node, beforeNode);
}

function randomMove(allNodes, nonRootNodes) {
  insertNodeAtRandom(allNodes, removeNodeAtRandom(nonRootNodes));
}

function insertAfter(parent, node, refNode) {
  parent.insertBefore(node, refNode ? refNode.nextSibling : parent.firstChild);
}

function deepCloneAndCreateMapping(target, map) {
  var clone = target.cloneNode(false);
  map.set(target, clone);
  for (var i = 0; i < target.childNodes.length; i++)
    clone.appendChild(deepCloneAndCreateMapping(target.childNodes[i], map));

  return clone;
}

function applyChanged(orig, clone, map, tracker) {

  function getClone(origNode) {
    if (!origNode)
      return origNode;
    var cloneNode = map.get(origNode);
    if (!cloneNode) {
      cloneNode = origNode.cloneNode(false);
      map.set(origNode, cloneNode);
    }

    return cloneNode;
  }

  function removeNode(node) {
    var cloneNode = getClone(node);
    if (cloneNode.parentNode)
      cloneNode.parentNode.removeChild(cloneNode);
  }

  function moveOrInsertNode(node) {
    var cloneNode = getClone(node);
    var cloneParent = getClone(node.parentNode);
    var clonePrev = getClone(node.previousSibling);

    // TODO(rafaelw): Handle the case where a move is effectively a noop.
    if (cloneParent !== cloneNode.parentNode ||
        clonePrev !== cloneNode.previousSibling) {
      insertAfter(cloneParent, cloneNode, clonePrev);
    }
  }

  var removed = tracker.getRemoved();
  var addedOrMoved = tracker.getChildlistChanges();

  // Process removals first
  removed.forEach(removeNode);

  // NOTE: Applying the changes can result in an attempting to add a child
  // to a parent which is presently an ancestor of the parent. This can occur
  // based on random ordering of moves. The way we handle this is to first
  // remove all changed nodes from their parents, then apply.
  addedOrMoved.forEach(removeNode);
  addedOrMoved.forEach(moveOrInsertNode);

  tracker.reset();
}

var TREE_SIZE = 512;
var PASSES = 64;
var MOVES_PER_PASS = 64;
var NON_DOC_ROOTS_MAX = 3;

function testAddedRemovedFuzzer() {
  var allNodes = []
  var nonRootNodes = [];

  // Generate random document.
  randomTree(testDiv, TREE_SIZE);
  getReachable(testDiv, allNodes);
  getReachable(testDiv, nonRootNodes, true);

  // Generate some fragments which lie outside the document.
  var nonDocCount = randInt(1, NON_DOC_ROOTS_MAX);
  for (var i = 0; i < nonDocCount; i++) {
    var nonDoc = randomNode();
    nonDoc.id = 'ext' + i;
    randomTree(nonDoc, randInt(Math.floor(TREE_SIZE / 8),
                               Math.floor(TREE_SIZE / 4)));
    getReachable(nonDoc, allNodes);
    getReachable(nonDoc, nonRootNodes, true);
  }

  startObserving();
  for (var pass = 0; pass < PASSES; pass++) {
    var map = new WeakMap;
    var clone = deepCloneAndCreateMapping(testDiv, map);

    var fastMap = new WeakMap;
    var fastClone = deepCloneAndCreateMapping(testDiv, fastMap);

    for (var move = 0; move < MOVES_PER_PASS; move++) {
      randomMove(allNodes, nonRootNodes);
    }

    document.deliverMutations();

    compareNodeArrayIgnoreOrder(tracker.getChangedParent(),
                                fastTracker.getChangedParent());

    applyChanged(testDiv, clone, map, tracker);
    assertTreesEqual(testDiv, clone);

    applyChanged(testDiv, fastClone, fastMap, fastTracker);
    assertTreesEqual(testDiv, fastClone);
  }
}

</script>
</body>
</html>
